package com.haiyou.dc.suanfa;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TestAdd {

    public static void main(String[] args) {

        int[] arr = {2, 4, 3, 7, 8, 10};
        int target = 9;

        System.out.println(Arrays.toString(m1(arr, target)));
        System.out.println(Arrays.toString(m2(arr, target)));

    }

    /**
     * 两个for循环
     *
     * @param arr
     * @param target
     * @return
     */
    public static Integer[] m1(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] + arr[j] == target) {
                    return new Integer[]{i, j};
                }
            }
        }
        return new Integer[]{0};
    }

    /**
     * 哈希法：key=值，value=索引
     *
     * @param arr
     * @param target
     * @return
     */
    public static Integer[] m2(int[] arr, int target) {
        Map<Integer, Integer> result = new HashMap<>();
        for (Integer i = 0; i < arr.length; i++) {
            Integer key = target - arr[i];
            if (result.containsKey(key)) {
                return new Integer[]{result.get(key), i};
            }
            result.put(arr[i], i);
        }
        return new Integer[]{0};
    }
}
